// A topological ordering is an ordering of the nodes in a directed graph
// where for each directed edge from node A to B， node A appears before 
// node B in the ordering.
// The topological sort algorithm can find a topological orering in O(V+E)
// time!
// Directed Acyclic Graphs (DAG)
// https://www.bilibili.com/video/BV11E411o7Fb?p=6
// A <———— B 
// B depends on A (Topological sort DFS)

#include <bits/stdc++.h>
using namespace std;

template <typename T>
vector<T> reverseVector(vector<T> &vec){
    int i = 0;
    int j = vec.size()-1;
    while(i < j){
        swap(vec[i],vec[j]);
        i++;
        j--;
    }
    return vec;
}
template <typename T>
void printVector(vector<T> nums)
{
    for (auto n : nums)
    {
        cout << char(n+'A') << ' ';
    }
    cout<<endl;
}

void dfs(int node, vector<bool>& V,vector<int>& visitedNodes, vector<vector<int>> &graph){
    V[node] = true;
    vector<int> edges = graph[node];
    for(int to : edges){
        if(V[to] == false){
            dfs(to,V,visitedNodes,graph);
        }
    }
    visitedNodes.push_back(node);
    return;
}


// Assumption: graph is stored as adjacency list
vector<int> topsort(vector<vector<int>> graph){
    int N = graph.size(); // number of nodes
    vector<bool> V(N);
    vector<int> ordering;

    for(int i = 0; i < N; i++){
        if(V[i] == false){
            vector<int> visitedNodes;
            dfs(i,V,visitedNodes,graph);
            for(auto nodeID : visitedNodes){
                ordering.push_back(nodeID);
            }
        }
    }
    return reverseVector(ordering);
}



int main(){
    vector<vector<int>> graph = {
        {'D'},
        {'D'},
        {'A','B'},
        {'H','G'},
        {'A','D','F'},
        {'J','K'},
        {'I'},
        {'I'},
        {'L'},
        {'L','M'},
        {'J'},
        {},
        {}
    };
    for(auto &a:graph){
        for(auto &b : a){
            b = b - 'A';
        }
    }
    printVector(topsort(graph));
    return 0;
}


